|
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles. In two dimensions, the problem can be solved in polynomial time in a model of computation allowing addition and comparisons of real numbers, despite theoretical difficulties involving the numerical precision needed to perform such calculations. These algorithms are based on two different principles, either performing a shortest path algorithm such as Dijkstra's algorithm on a visibility graph derived from the obstacles or (in an approach called the ''continuous Dijkstra'' method) propagating a wavefront from one of the points until it meets the other. In three (and higher) dimensions the problem is NP-hard in the general case ,〔 J. Canny and J. H. Reif, "New lower bound techniques for robot motion planning problems", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49-60. 〕 but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points. There are many results on computing shortest paths which stays on a polyhedral surface. Given two points s and t, say on the surface of a convex polyhedron, the problem is to compute a shortest path that never leaves the surface and connects s with t. This is a generalization of the problem from 2-dimension but it is much easier than the 3-dimensional problem. Also, there are variations of this problem, where the obstacles are ''weighted'', i.e., one can go through an obstacle, but it incurs an extra cost to go through an obstacle. The standard problem is the special case where the obstacles have infinite weight. This is termed as the ''weighted region problem'' in the literature. ==See also== *Shortest path problem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Euclidean shortest path」の詳細全文を読む スポンサード リンク
|